A computer network is a geographically distributed collection of interconnected communication links and segments for transporting data between nodes, such as computers. Many types of network segments are available, with the types ranging from local area networks (LAN) to wide area networks (WAN). For example, the LAN may typically connect personal computers and workstations over dedicated, private communications links, whereas the WAN may connect large numbers of nodes over long-distance communications links, such as common carrier telephone lines. The Internet is an example of a WAN that connects disparate networks throughout the world, providing global communication between nodes on various networks. The nodes typically communicate over the network by exchanging discrete frames or packets of data according to predefined protocols. In this context, a protocol consists of a set of rules defining how the nodes interact with each other.
Computer networks may be further interconnected by an intermediate network node, such as a switch or router, having a plurality of ports that may be coupled to the networks. To interconnect dispersed computer networks and/or provide Internet connectivity, many organizations rely on the infrastructure and facilities of Internet Service Providers (ISPs). ISPs typically own one or more backbone networks that are configured to provide high-speed connection to the Internet. To interconnect private networks that are geographically diverse, an organization may subscribe to one or more ISPs and couple each of its private networks to the ISP's equipment. Here, the router may be utilized to interconnect a plurality of private networks or subscribers to an IP “backbone” network. Routers typically operate at the network layer, i.e., layer 3, of a communications protocol stack, such as the internetwork layer of the Transmission Control Protocol/Internet Protocol (TCP/IP) communications architecture.
Simple networks may be constructed using general-purpose routers interconnected by links owned or leased by ISPs. As networks become more complex with greater numbers of elements, additional structure may be required. In a complex network, structure can be imposed on routers by assigning specific jobs to particular routers. A common approach for ISP networks is to divide assignments among access routers and backbone routers. An access router provides individual subscribers access to the network by way of large numbers of relatively low-speed ports connected to the subscribers. Backbone routers, on the other hand, provide transports to Internet backbones and are configured to provide high forwarding rates on fast interfaces. ISPs may impose further physical structure on their networks by organizing them into points of presence (POP). An ISP network usually consists of a number of POPs, each of which comprises a physical location wherein a set of access and backbone routers is located.
As Internet traffic increases, the demand for access routers to handle increased density and backbone routers to handle greater throughput becomes more important. In this context, increased density denotes a greater number of subscriber ports that can be terminated on a single router. Such requirements can be met most efficiently with platforms designed for specific applications. An example of such a specifically designed platform is an aggregation router. The aggregation router is an access router configured to provide high quality of service and guaranteed bandwidth for both data and voice traffic destined for the Internet. The aggregation router also provides a high degree of security for such traffic. These functions are considered “high-touch” features that necessitate substantial processing of the traffic by the router. More notably, the aggregation router is configured to accommodate increased density by aggregating a large number of leased lines from ISP subscribers onto a few trunk lines coupled to an Internet backbone.
In addition to deployment at a POP, the aggregation router may be deployed in a telephone company central office. The large numbers of subscribers connected to input interface ports of the router are typically small to medium sized businesses that conduct a substantial portion of their operations “on-line”, e.g., over the Internet. Each of these subscribers may connect to the aggregation router over a high reliability link connection that is typically leased from, e.g., a telephone company provider. The subscriber traffic received at the input interfaces is funneled onto at least one trunk interface. That is, the aggregation router essentially functions as a large “fan-in” device wherein a plurality (e.g., thousands) of relatively low-speed subscriber input links is aggregated onto a single, high-speed output trunk to a backbone network of the Internet.
Broadly stated, each input link may comprise a T1 or T3 connection, whereas the output trunk interface connection may comprise an OC-12 connection. A T1 connection has a data rate of 1.5 megabits per seconds (Mbps) and there are 28 T1s to each T3 connection; a T3 connection thus has an effective data rate of approximately 42 Mbps. On the other hand, the effective data rate of an OC-12 trunk interface connection is typically 622 Mbps. As noted, the aggregation router receives a plurality of subscriber inputs and aggregates them onto a single output trunk. However, not all inputs are constantly in use and, through the use of statistical multiplexing, the number of input subscriber lines that can be disposed over a single output trunk at one time can be determined.
The advent of large-scale, channelized interfaces has resulted in a vast number of channels that can be created as virtual interfaces over a single physical connection. Channelized T3 (CT3) is an example of a line card having such interfaces. Typically, each T3 port of a CT3 line card can be configured into 28 T1s and each T1 can be configured into 24 DS0 channels for a maximum of 672 interfaces per port. Here, an interface may be defined as an element that can be referenced by the combination of a slot (i.e., line card) number, port number and channel number of a router. The channels or DS0 “time slots” may represent subscribers, each of which may have varying bandwidth up to the maximum bandwidth of the T1.
In an implementation of an aggregation router having a network processor, the computing architecture may comprise a multiprocessing environment configured as a matrix of processors that operate in a parallel (column-wise) as well as a pipeline (row-wise) fashion. Packets enter the computing matrix on a quasi-randomly selected pipeline row of the matrix and each column of processors processes the packets in accordance with a designated task, i.e., feature. Upon entering the matrix, each packet is classified according to the interface over which it is received at the router. Each processor of a column may need to “lookup” configuration information, such as state, statistical and configuration data, stored in memory and that are utilized in the classification and routing of the packet through the system. Once it completes its processing task, the processor passes the packet to a processor in a next column of the matrix.
A database comprising various data structures may be used to organize the configuration information in the memory. At a specific instance in time as the packets move through the computing matrix, different packets are at different processor locations within the matrix. If changes or updates need to be made to these data structures, it is desirable that they be done in a fashion that does not disrupt the coherency of the database or packets currently being processed by the matrix. Data coherency is needed to maintain the stability of the computing environment as well as the integrity of packet data. A partially updated database could result in processor exceptions, processing loops, corrupted packet data, incorrect statistics, etc.
One approach that may be used to maintain data coherency is to prevent new packets from entering the matrix until all current packets are completely processed, i.e., wait for the pipelines to “drain”. However, this approach is inefficient since it requires stalling of some, if not most, of the processors for the period of time needed to drain the pipelines. For a multiprocessing environment where there are many (e.g., greater than 8,000) configurable entries in the database and where packets are allowed to make multiple “passes” through the computing matrix, this period of time may be substantial.
For example, assume the processors of the matrix are arrayed in a 4-row by 8 column configuration. In addition, assume a clock cycle period for the matrix is 10 nanoseconds and the number of cycles allotted per column of processors to complete processing is 100. The time consumed to enable all of the packets to exit the matrix in a single pass through the pipeline rows is thus 8 microseconds (i.e., 8 columns×100 cycles per column×10 nanoseconds per cycle). For those packets requiring multiple passes through the matrix, 8 microseconds per pass are consumed. Assume further that the database requires updating and that the pipelines of the matrix are drained prior to such updating. Therefore, a substantial portion of the processor resources is “wasted” (stalled) for tens of microseconds each time the database is updated. If the frequency of updates is high, performance of the computing matrix, and the router, is adversely impacted. The present invention is directed, in part, to obviating the need to stall packet processing within the computing matrix during updates of the configuration information database.
The lookup operations used to access the configuration information may be based on either the input interface over which the packet was received at the router or the output interface over which the packet is transmitted from the router, depending on the feature that is currently processing the packet. In addition, the packet may be received at or transmitted from the router in connection with a session that is established over the input or output interface. The input and/or output interface may comprise either a physical interface or a virtual interface wherein, in this context, the physical interface provides “dedicated” bandwidth to the session, whereas the virtual interface does not dedicate its entire bandwidth to the session. That is, the virtual interface session must contend for bandwidth with other protocols, such as layer 2 protocols, running over that interface.
The configuration lookup operation typically involves the use of a conventional mapping table wherein an index associated with either the physical interface (i.e., the physical interface index) or the virtual interface (i.e., the virtual interface index) is provided to the table which, in turn, generates a “handle”. The handle may then be used to lookup (access) certain configuration-related information on a per packet basis for the routing and classification features implemented by the computing architecture. In a multiprocessing environment wherein multiple processors “act on” (process) a single packet, each processor may be responsible for determining the input/output interface type needed to generate the handle used to access the configuration information. This results in the need to test for interface types many times during the course of packet processing. Since the computing matrix of a network processor based router limits the number of cycles and bandwidth allocated to a configuration lookup operation, it is important to be as efficient as possible in terms of memory bandwidth and processor cycles. The present invention is also directed, in part, to providing a unique handle that may be used across the pipeline of processors to access configuration information stored in the memory associated with the matrix.
An issue associated with the conventional mapping table is that use of the physical and virtual interface indexes requires an arbitrarily large configuration information database. For example, assume the physical interface index is a 21-bit value derived from a combination of a particular channel associated with the physical interface and a particular line card of the router associated with the channel. The 21-bit physical interface index yields 2 million possible physical interfaces (values), each of which may have associated virtual interfaces (values). These virtual interfaces have associated virtual circuit identifier values that may range from a 10-bit frame relay data link control identifier (DLCI) value to a 24-bit asynchronous transfer mode (ATM) virtual path identifier (VPI)/ virtual channel identifier (VCI) value. Therefore, the lookup “address” space of the database may be 45 bits (or 35,184,372,088,832 entries) which is generally unmanageable. Moreover, if each entry consumed only 1 byte of data, this would represent approximately 35 terabytes of information that, in turn, would require an impractical amount of memory. (Note that 10 terabytes is the printed collection of the US Library of Congress.) The present invention is further directed to reducing the lookup address space of a configuration information database to a manageable space that can be used in a multiprocessing environment.